{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Number of Teams"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numTeams"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计作战单位数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p> <code>n</code> 名士兵站成一排。每个士兵都有一个 <strong>独一无二</strong> 的评分 <code>rating</code> 。</p>\n",
    "\n",
    "<p>每 <strong>3</strong> 个士兵可以组成一个作战单位，分组规则如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从队伍中选出下标分别为 <code>i</code>、<code>j</code>、<code>k</code> 的 3 名士兵，他们的评分分别为 <code>rating[i]</code>、<code>rating[j]</code>、<code>rating[k]</code></li>\n",
    "\t<li>作战单位需满足： <code>rating[i] < rating[j] < rating[k]</code> 或者 <code>rating[i] > rating[j] > rating[k]</code> ，其中  <code>0 <= i < j < k < n</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rating = [2,5,3,4,1]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>我们可以组建三个作战单位 (2,3,4)、(5,4,1)、(5,3,1) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rating = [2,1,3]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>根据题目条件，我们无法组建作战单位。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rating = [1,2,3,4]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == rating.length</code></li>\n",
    "\t<li><code>3 <= n <= 1000</code></li>\n",
    "\t<li><code>1 <= rating[i] <= 10^5</code></li>\n",
    "\t<li><code>rating</code> 中的元素都是唯一的</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-number-of-teams](https://leetcode.cn/problems/count-number-of-teams/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-number-of-teams](https://leetcode.cn/problems/count-number-of-teams/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,5,3,4,1]', '[2,1,3]', '[1,2,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        ans = 0\n",
    "        # 枚举三元组中的 j\n",
    "        for j in range(1, n - 1):\n",
    "            iless = imore = kless = kmore = 0\n",
    "            for i in range(j):\n",
    "                if rating[i] < rating[j]:\n",
    "                    iless += 1\n",
    "                # 注意这里不能直接写成 else\n",
    "                # 因为可能有评分相同的情况\n",
    "                elif rating[i] > rating[j]:\n",
    "                    imore += 1\n",
    "            for k in range(j + 1, n):\n",
    "                if rating[k] < rating[j]:\n",
    "                    kless += 1\n",
    "                elif rating[k] > rating[j]:\n",
    "                    kmore += 1\n",
    "            ans += iless * kmore + imore * kless\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        ans = 0\n",
    "        for j in range(n-1):\n",
    "            iless = imore = kless = kmore = 0\n",
    "            for i in range(j):\n",
    "                if rating[j] > rating[i]:\n",
    "                    iless += 1\n",
    "                elif rating[i] > rating[j]:\n",
    "                    imore += 1\n",
    "            for k in range(j+1, n):\n",
    "                if rating[k] < rating[j]:\n",
    "                    kless += 1\n",
    "                elif rating[k] > rating[j]:\n",
    "                    kmore += 1\n",
    "            ans += iless * kmore + imore * kless\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(rating)\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i + 1, n):\n",
    "        #         if rating[j] > rating[i]:\n",
    "        #             for k in range(j + 1, n):\n",
    "        #                 if rating[k] > rating[j]:\n",
    "        #                     ans += 1\n",
    "        #         else:\n",
    "        #             for k in range(j + 1, n):\n",
    "        #                 if rating[k] < rating[j]:\n",
    "        #                     ans += 1 \n",
    "        for j in range(1, n):\n",
    "            less_left, more_right = 0, 0\n",
    "            less_right, more_left = 0, 0\n",
    "            for i in range(j):\n",
    "                if rating[i] < rating[j]:\n",
    "                    less_left += 1\n",
    "                else:\n",
    "                    more_left += 1\n",
    "            for i in range(j + 1, n):\n",
    "                if rating[i] < rating[j]:\n",
    "                    less_right += 1\n",
    "                else:\n",
    "                    more_right += 1\n",
    "            ans += (less_left * more_right) \n",
    "            ans += (less_right * more_left) \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        result = 0\n",
    "\n",
    "        for i in range(1, n-1):  # 只从数组的两端开始遍历\n",
    "            left_smaller, left_larger = 0, 0\n",
    "            right_smaller, right_larger = 0, 0\n",
    "\n",
    "            for j in range(i):\n",
    "                if rating[j] < rating[i]:\n",
    "                    left_smaller += 1\n",
    "                else:\n",
    "                    left_larger += 1\n",
    "\n",
    "            for j in range(i + 1, n):\n",
    "                if rating[j] < rating[i]:\n",
    "                    right_smaller += 1\n",
    "                else :\n",
    "                    right_larger += 1\n",
    "\n",
    "            result += left_smaller * right_larger + left_larger * right_smaller\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "       n = len(rating)\n",
    "       res = 0\n",
    "       for i in range(1, n - 1):\n",
    "          cnt1 = 0\n",
    "          cnt2 = 0\n",
    "          j = i - 1\n",
    "          while j >= 0:\n",
    "             if rating[j] < rating[i]:\n",
    "                cnt1 += 1\n",
    "             elif rating[j] > rating[i]:\n",
    "                cnt2 += 1\n",
    "             j -= 1\n",
    "          cnt3 = 0\n",
    "          cnt4 = 0\n",
    "          j = i + 1\n",
    "          while j < n:\n",
    "             if rating[j] < rating[i]:\n",
    "                cnt3 += 1\n",
    "             elif rating[j] > rating[i]:\n",
    "                cnt4 += 1\n",
    "             j += 1\n",
    "          res += cnt1 * cnt4\n",
    "          res += cnt2 * cnt3\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        result = 0\n",
    "\n",
    "        for i in range(1, n-1):  # 只从数组的两端开始遍历\n",
    "            left_smaller, left_larger = 0, 0\n",
    "            right_smaller, right_larger = 0, 0\n",
    "\n",
    "            for j in range(i):\n",
    "                if rating[j] < rating[i]:\n",
    "                    left_smaller += 1\n",
    "                else:\n",
    "                    left_larger += 1\n",
    "\n",
    "            for j in range(i + 1, n):\n",
    "                if rating[j] < rating[i]:\n",
    "                    right_smaller += 1\n",
    "                else :\n",
    "                    right_larger += 1\n",
    "\n",
    "            result += left_smaller * right_larger + left_larger * right_smaller\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        ans = 0\n",
    "        # 枚举三元组中的 j\n",
    "        for j in range(1, n - 1):\n",
    "            iless = imore = kless = kmore = 0\n",
    "            for i in range(j):\n",
    "                if rating[i] < rating[j]:\n",
    "                    iless += 1\n",
    "                # 注意这里不能直接写成 else\n",
    "                # 因为可能有评分相同的情况\n",
    "                elif rating[i] > rating[j]:\n",
    "                    imore += 1\n",
    "            for k in range(j + 1, n):\n",
    "                if rating[k] < rating[j]:\n",
    "                    kless += 1\n",
    "                elif rating[k] > rating[j]:\n",
    "                    kmore += 1\n",
    "            ans += iless * kmore + imore * kless\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating) \n",
    "        res = 0\n",
    "        for j in range(1, n-1):\n",
    "            ilow = ihigh = klow = khigh = 0\n",
    "            for i in range(j):\n",
    "                if rating[i] < rating[j]:\n",
    "                    ilow += 1\n",
    "                elif rating[i] > rating[j]:\n",
    "                    ihigh += 1\n",
    "            for k in range(j+1, n):\n",
    "                if rating[k] > rating[j]:\n",
    "                    khigh += 1\n",
    "                elif rating[k] < rating[j]:\n",
    "                    klow += 1\n",
    "            res +=(ihigh * klow + ilow * khigh)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        def get(i):\n",
    "            x = rating[i]\n",
    "            less = more = 0\n",
    "            for e in rating[:i]:\n",
    "                if (e < x): less += 1\n",
    "                elif (e > x): more += 1\n",
    "            less1 = more1 = 0\n",
    "            for e in rating[i+1:]:\n",
    "                if (e < x): less1 += 1\n",
    "                elif (e > x): more1 += 1\n",
    "            return less * more1 + more * less1\n",
    "        return sum(get(i) for i in range(1, n - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        \n",
    "        def lowbit(x):          # lowbit函数：二进制最低位1所表示的数字\n",
    "            return x & (-x)\n",
    "\n",
    "        def add(i, delta):      # 单点更新：执行+delta\n",
    "            while i<len(tree):\n",
    "                tree[i] += delta\n",
    "                i += lowbit(i)\n",
    "\n",
    "        def query(i):           # 前缀和查询\n",
    "            presum = 0\n",
    "            while i>0:\n",
    "                presum += tree[i]\n",
    "                i -= lowbit(i)\n",
    "            return presum\n",
    "\n",
    "\n",
    "        '''主程序'''\n",
    "        # 离散化：绝对数值转秩次rank\n",
    "        uniques = sorted(rating)    # rating没有重复值\n",
    "        rank_map = {v:i+1 for i,v in enumerate(uniques)}    #【rank从1开始】\n",
    "        \n",
    "        # 构建树状数组\n",
    "        tree = [0] * (len(rank_map) + 1)    # 树状数组下标从1开始\n",
    "\n",
    "        # 枚举中间点\n",
    "        ans = 0\n",
    "        n = len(rating)\n",
    "        add(rank_map[rating[0]], 1)     # 先将第一个元素入列\n",
    "        for i in range(1, n-1):         # 从第二个元素开始遍历，直至倒数第二个元素\n",
    "            rank = rank_map[rating[i]]  # 当前元素的排名/秩次\n",
    "\n",
    "            small1 = query(rank-1)      # 查询前序元素中排名<rank的元素数目\n",
    "            large1 = i - small1         # small1 + large1 = i\n",
    "\n",
    "            small2 = (rank-1) - small1  # 共有rank-1个元素排名<rank：small1 + small2 = rank-1\n",
    "            large2 = n-1 - i - small2   # small2 + large2 = n-1-i\n",
    "\n",
    "            add(rank, 1)                # 当前元素入列\n",
    "\n",
    "            ans += small1*large2 + large1*small2\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        count = [0 for i in range(n)]\n",
    "        for i in range(n-1):\n",
    "            num = 0\n",
    "            for j in range(i+1,n):\n",
    "                if rating[j] > rating[i]:\n",
    "                    num += 1\n",
    "            count[i] = num\n",
    "        sum_num = 0\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if rating[j] > rating[i]:\n",
    "                    sum_num += count[j]\n",
    "                else:\n",
    "                    sum_num += n - 1 - j - count[j]\n",
    "        return sum_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        result = 0\n",
    "\n",
    "        for i in range(1, n-1):  # 只从数组的两端开始遍历\n",
    "            left_smaller, left_larger = 0, 0\n",
    "            right_smaller, right_larger = 0, 0\n",
    "\n",
    "            for j in range(i):\n",
    "                if rating[j] < rating[i]:\n",
    "                    left_smaller += 1\n",
    "                else:\n",
    "                    left_larger += 1\n",
    "\n",
    "            for j in range(i + 1, n):\n",
    "                if rating[j] < rating[i]:\n",
    "                    right_smaller += 1\n",
    "                else :\n",
    "                    right_larger += 1\n",
    "\n",
    "            result += left_smaller * right_larger + left_larger * right_smaller\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            c1, c2 = 0, 0\n",
    "            for j in range(i):\n",
    "                if rating[j] < rating[i]:\n",
    "                    c1 += 1\n",
    "            for j in range(i + 1, n):\n",
    "                if rating[j] > rating[i]:\n",
    "                    c2 += 1\n",
    "            res += c1 * c2 + (i - c1) * (n - i - 1 - c2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        res = 0\n",
    "        for mid in range(len(rating)):\n",
    "            left_up = 0\n",
    "            left_down = 0\n",
    "            for left in range(mid):\n",
    "                if rating[left] < rating[mid]:\n",
    "                    left_down += 1\n",
    "                else:\n",
    "                    left_up += 1\n",
    "            right_up = 0\n",
    "            right_down = 0\n",
    "            for right in range(mid+1, len(rating)):\n",
    "                if rating[right] < rating[mid]:\n",
    "                    right_down += 1\n",
    "                else:\n",
    "                    right_up += 1\n",
    "            res += left_up * right_down + left_down * right_up\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT1:\n",
    "    \"\"\"单点修改,区间和查询\"\"\"\n",
    "\n",
    "    __slots__ = \"size\", \"bit\", \"tree\"\n",
    "\n",
    "    def __init__(self, n: int):\n",
    "        self.size = n\n",
    "        self.bit = n.bit_length()\n",
    "        self.tree = [0]*(n+1)\n",
    "\n",
    "    def add(self, index: int, delta: int) -> None:\n",
    "        # index 必须大于0\n",
    "        while index <= self.size:\n",
    "            self.tree[index]+=delta\n",
    "            index += index & -index\n",
    "\n",
    "    def _query(self, index: int) -> int: \n",
    "        res = 0\n",
    "        while index > 0:\n",
    "            res += self.tree[index]\n",
    "            index -= index & -index\n",
    "        return res\n",
    "\n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        return self._query(right) - self._query(left - 1)\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        res=0\n",
    "        arr=sorted(set(rating))\n",
    "        d={a:i+1 for i,a in enumerate(arr)}\n",
    "        n=len(arr)+5\n",
    "        b1=BIT1(n)\n",
    "        b2=BIT1(n)\n",
    "        b3=BIT1(n)\n",
    "        b4=BIT1(n)\n",
    "        for a in rating:\n",
    "            res+=b2.query(1,d[a]-1)\n",
    "            res+=b4.query(d[a]+1,n)\n",
    "            b2.add(d[a],b1.query(1,d[a]-1))\n",
    "            b1.add(d[a],1)\n",
    "            b4.add(d[a],b3.query(d[a]+1,n))\n",
    "            b3.add(d[a],1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(rating)\n",
    "        for i in range(1, n-1):\n",
    "            small1 = 0 \n",
    "            for j in range(i):\n",
    "                if rating[j] < rating[i]:\n",
    "                    small1 += 1\n",
    "\n",
    "            large1 = i - small1\n",
    "\n",
    "            small2 = 0 \n",
    "            for j in range(i+1, n):\n",
    "                if rating[j] < rating[i]:\n",
    "                    small2 += 1\n",
    "\n",
    "            large2 = n-1 - i - small2\n",
    "\n",
    "            ans += small1*large2 + large1*small2\n",
    "        \n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        ans = 0\n",
    "        for i in range(1,n-1):\n",
    "            ans_l = 0\n",
    "            ans_r = 0\n",
    "            for x in rating[:i]:\n",
    "                if x > rating[i]:\n",
    "                    ans_l +=1\n",
    "            for x in rating[i+1:]:\n",
    "                if x > rating[i]:\n",
    "                    ans_r +=1\n",
    "            ans += ans_l*(n-i-1-ans_r) + (i-ans_l)*ans_r\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i, v in enumerate(rating):\n",
    "            llt = rlt = lgt = rgt = 0\n",
    "            for j, x in enumerate(rating):\n",
    "                if x < v:\n",
    "                    if j < i:\n",
    "                        llt += 1\n",
    "                    else:\n",
    "                        rlt += 1\n",
    "                if x > v:\n",
    "                    if j < i:\n",
    "                        lgt += 1\n",
    "                    else:\n",
    "                        rgt += 1\n",
    "            ans += (llt * rgt) + (lgt * rlt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        ans = 0\n",
    "        # 枚举三元组中的 j\n",
    "        for j in range(1, n - 1):\n",
    "            iless = imore = kless = kmore = 0\n",
    "            for i in range(j):\n",
    "                if rating[i] < rating[j]:\n",
    "                    iless += 1\n",
    "                # 注意这里不能直接写成 else\n",
    "                # 因为可能有评分相同的情况\n",
    "                elif rating[i] > rating[j]:\n",
    "                    imore += 1\n",
    "            for k in range(j + 1, n):\n",
    "                if rating[k] < rating[j]:\n",
    "                    kless += 1\n",
    "                elif rating[k] > rating[j]:\n",
    "                    kmore += 1\n",
    "            ans += iless * kmore + imore * kless\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        ans = 0\n",
    "        # 扩散法\n",
    "        for i, n in enumerate(rating[1:-1], 1):\n",
    "            left_small = sum(m < n for m in rating[:i])\n",
    "            left_big = sum(m > n for m in rating[:i])\n",
    "            right_small = sum(m < n for m in rating[i+1:])\n",
    "            right_big = sum(m > n for m in rating[i+1:])\n",
    "            ans += left_small * right_big + left_big * right_small\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        pre1 = [0] * n \n",
    "        pre2 = [0] * n \n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if rating[j] < rating[i]:\n",
    "                    pre1[i] += 1\n",
    "                if rating[j] > rating[i]:\n",
    "                    pre2[i] += 1\n",
    "        ans = 0 \n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if rating[j] < rating[i]:\n",
    "                    ans += pre1[j] \n",
    "                if rating[j] > rating[i]:\n",
    "                    ans += pre2[j] \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        dg = [0]*n\n",
    "        dgf = [0]*n\n",
    "        fh = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if rating[j] < rating[i]:\n",
    "                    if dg[j]:\n",
    "                        fh += dg[j]\n",
    "                    dg[i] += 1\n",
    "                else:\n",
    "                    if dgf[j]:\n",
    "                        fh += dgf[j]\n",
    "                    dgf[i] += 1\n",
    "        return fh\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        a = len(rating)\n",
    "        sum = 0\n",
    "        for i in range(1, a-1):    # i从1便历到8\n",
    "            zuo = 0\n",
    "            you = a-1\n",
    "            zuoxiao, youxiao = 0, 0\n",
    "            zuoda, youda = 0, 0\n",
    "            while zuo < i:\n",
    "                if rating[zuo] < rating[i]:\n",
    "                    zuoxiao += 1\n",
    "                else:\n",
    "                    zuoda += 1\n",
    "                zuo += 1\n",
    "            while you > i:\n",
    "                if rating[i] > rating[you]:\n",
    "                    youxiao += 1\n",
    "                else:\n",
    "                    youda += 1\n",
    "                you -= 1\n",
    "            sum += zuoxiao*youda+zuoda*youxiao\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        pre_b = [0] * n\n",
    "        pre_s = [0] * n\n",
    "        for i in range(1, n):\n",
    "            cur_b = 0\n",
    "            cur_s = 0\n",
    "            for j in range(0, i):\n",
    "                cur_b += 1 if rating[j] > rating[i] else 0\n",
    "                cur_s += 1 if rating[j] < rating[i] else 0\n",
    "            pre_b[i] = cur_b\n",
    "            pre_s[i] = cur_s\n",
    "        suf_b = [0] * n\n",
    "        suf_s = [0] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            cur_b = 0\n",
    "            cur_s = 0\n",
    "            for j in range(n-1, i, -1):\n",
    "                cur_b += 1 if rating[j] > rating[i] else 0\n",
    "                cur_s += 1 if rating[j] < rating[i] else 0\n",
    "            suf_b[i] = cur_b\n",
    "            suf_s[i] = cur_s\n",
    "        res = 0\n",
    "        for j in range(1, n-1):\n",
    "            res += pre_b[j] * suf_s[j] + pre_s[j] * suf_b[j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        a = len(rating)\n",
    "        sum = 0\n",
    "        for i in range(1, a-1):    # i从1便历到8\n",
    "            zuo = 0\n",
    "            you = a-1\n",
    "            zuoxiao, youxiao = 0, 0\n",
    "            zuoda, youda = 0, 0\n",
    "            while zuo < i:\n",
    "                if rating[zuo] < rating[i]:\n",
    "                    zuoxiao += 1\n",
    "                else:\n",
    "                    zuoda += 1\n",
    "                zuo += 1\n",
    "            while you > i:\n",
    "                if rating[i] > rating[you]:\n",
    "                    youxiao += 1\n",
    "                else:\n",
    "                    youda += 1\n",
    "                you -= 1\n",
    "            sum += zuoxiao*youda+zuoda*youxiao\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        result = 0\n",
    "\n",
    "        for i in range(1, n-1):  # 只从数组的两端开始遍历\n",
    "            left_smaller, left_larger = 0, 0\n",
    "            right_smaller, right_larger = 0, 0\n",
    "\n",
    "            for j in range(i):\n",
    "                if rating[j] < rating[i]:\n",
    "                    left_smaller += 1\n",
    "                else:\n",
    "                    left_larger += 1\n",
    "\n",
    "            for j in range(i + 1, n):\n",
    "                if rating[j] < rating[i]:\n",
    "                    right_smaller += 1\n",
    "                else :\n",
    "                    right_larger += 1\n",
    "\n",
    "            result += left_smaller * right_larger + left_larger * right_smaller\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        dg = [0]*n\n",
    "        dgf = [0]*n\n",
    "        fh = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if rating[j] < rating[i]:\n",
    "                    if dg[j]:\n",
    "                        fh += dg[j]\n",
    "                    dg[i] += 1\n",
    "                else:\n",
    "                    if dgf[j]:\n",
    "                        fh += dgf[j]\n",
    "                    dgf[i] += 1\n",
    "        return fh\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for j in range(len(rating)):\n",
    "            mid = rating[j]\n",
    "            l_more,l_less=0,0\n",
    "            for i in range(j):\n",
    "                if rating[i] > mid:\n",
    "                    l_more += 1\n",
    "                elif rating[i] < mid:\n",
    "                    l_less += 1\n",
    "\n",
    "            r_more,r_less = 0,0\n",
    "            for k in range(j+1,len(rating)):\n",
    "                if rating[k] >  mid:\n",
    "                    r_more += 1\n",
    "                elif rating[k] < mid:\n",
    "                    r_less += 1\n",
    "                \n",
    "            ans += l_less*r_more + l_more*r_less\n",
    "        return ans           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        ans=0\n",
    "        n=len(rating)\n",
    "        for i in range(n):\n",
    "            rightmax=0\n",
    "            rightmin=0\n",
    "            leftmax=0\n",
    "            leftmin=0\n",
    "            num=rating[i]\n",
    "            for j in range(i):\n",
    "                if rating[j]>num:\n",
    "                    leftmax+=1\n",
    "                if rating[j]<num:\n",
    "                    leftmin+=1\n",
    "            \n",
    "            for k in range(i+1,n):\n",
    "                if rating[k]>num:\n",
    "                    rightmax+=1\n",
    "                if rating[k]<num:\n",
    "                    rightmin+=1\n",
    "            ans+=leftmax*rightmin+leftmin*rightmax\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        result = 0\n",
    "\n",
    "        for i in range(1, n-1):  # 只从数组的两端开始遍历\n",
    "            left_smaller, left_larger = 0, 0\n",
    "            right_smaller, right_larger = 0, 0\n",
    "\n",
    "            for j in range(i):\n",
    "                if rating[j] < rating[i]:\n",
    "                    left_smaller += 1\n",
    "                else:\n",
    "                    left_larger += 1\n",
    "\n",
    "            for j in range(i + 1, n):\n",
    "                if rating[j] < rating[i]:\n",
    "                    right_smaller += 1\n",
    "                else :\n",
    "                    right_larger += 1\n",
    "\n",
    "            result += left_smaller * right_larger + left_larger * right_smaller\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            x = rating[i]\n",
    "            before = rating[:i][:]\n",
    "            after = rating[i+1:][:]\n",
    "            before.sort()\n",
    "            after.sort()\n",
    "            before_index = bisect.bisect_left(before, x)\n",
    "            after_index = bisect.bisect_left(after, x)\n",
    "\n",
    "            ans += before_index * (n - 1 - i - after_index) + (i - before_index) * after_index\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        # i,j,k, 遍历j,再在j的左边数组遍历i,右边数组遍历k\n",
    "        for j in range(1, n-1):\n",
    "            imore = kless = iless = kmore = 0\n",
    "            for i in range(j):\n",
    "                if rating[i] > rating[j]:\n",
    "                    imore += 1\n",
    "                else:\n",
    "                    iless += 1\n",
    "            \n",
    "            for k in range(j+1, n):\n",
    "                if rating[k] > rating[j]:\n",
    "                    kmore += 1\n",
    "                else:\n",
    "                    kless += 1\n",
    "\n",
    "            ans += imore * kless + iless * kmore\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        ans = 0\n",
    "        # 枚举三元组中的 j\n",
    "        for j in range(1, n - 1):\n",
    "            iless = imore = kless = kmore = 0\n",
    "            for i in range(j):\n",
    "                if rating[i] < rating[j]:\n",
    "                    iless += 1\n",
    "                # 注意这里不能直接写成 else\n",
    "                # 因为可能有评分相同的情况\n",
    "                elif rating[i] > rating[j]:\n",
    "                    imore += 1\n",
    "            for k in range(j + 1, n):\n",
    "                if rating[k] < rating[j]:\n",
    "                    kless += 1\n",
    "                elif rating[k] > rating[j]:\n",
    "                    kmore += 1\n",
    "            ans += iless * kmore + imore * kless\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        a = len(rating)\n",
    "        sum = 0\n",
    "        for i in range(1, a-1):    # i从1便历到8\n",
    "            zuo = 0\n",
    "            you = a-1\n",
    "            zuoxiao, youxiao = 0, 0\n",
    "            zuoda, youda = 0, 0\n",
    "            while zuo < i:\n",
    "                if rating[zuo] < rating[i]:\n",
    "                    zuoxiao += 1\n",
    "                else:\n",
    "                    zuoda += 1\n",
    "                zuo += 1\n",
    "            while you > i:\n",
    "                if rating[i] > rating[you]:\n",
    "                    youxiao += 1\n",
    "                else:\n",
    "                    youda += 1\n",
    "                you -= 1\n",
    "            sum += zuoxiao*youda+zuoda*youxiao\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        ans = 0\n",
    "        # 枚举三元组中的 j\n",
    "        for j in range(1, n - 1):\n",
    "            iless = imore = kless = kmore = 0\n",
    "            for i in range(j):\n",
    "                if rating[i] < rating[j]:\n",
    "                    iless += 1\n",
    "                # 注意这里不能直接写成 else\n",
    "                # 因为可能有评分相同的情况\n",
    "                elif rating[i] > rating[j]:\n",
    "                    imore += 1\n",
    "            for k in range(j + 1, n):\n",
    "                if rating[k] < rating[j]:\n",
    "                    kless += 1\n",
    "                elif rating[k] > rating[j]:\n",
    "                    kmore += 1\n",
    "            ans += iless * kmore + imore * kless\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n=len(rating)\n",
    "        '''\n",
    "            up和down记录[0,i-1]有多少比i小的和比i大的\n",
    "        '''\n",
    "        up,down=[0]*n,[0]*n\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if rating[j]>rating[i]:\n",
    "                    #相当于是降序，找j前面多少个比rating[j]大的\n",
    "                    res+=down[j]\n",
    "                    down[i]+=1\n",
    "                elif rating[j]<rating[i]:\n",
    "                    #相当于升序，找j前面多少个比rating[j]小的\n",
    "                    res+=up[j]\n",
    "                    up[i]+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, a: List[int]) -> int:\n",
    "        res, n = 0, len(a)\n",
    "        for i in range(1, n - 1):\n",
    "            lm = ls = 0\n",
    "            for j in range(i):\n",
    "                if a[j] > a[i]:\n",
    "                    lm += 1\n",
    "                else: ls += 1\n",
    "            for j in range(i + 1, n):\n",
    "                if a[j] > a[i]:\n",
    "                    res += ls\n",
    "                else:\n",
    "                    res += lm\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        result = 0\n",
    "\n",
    "        for i in range(1, n-1):  # 只从数组的两端开始遍历\n",
    "            left_smaller, left_larger = 0, 0\n",
    "            right_smaller, right_larger = 0, 0\n",
    "\n",
    "            for j in range(i):\n",
    "                if rating[j] < rating[i]:\n",
    "                    left_smaller += 1\n",
    "                else:\n",
    "                    left_larger += 1\n",
    "\n",
    "            for j in range(i + 1, n):\n",
    "                if rating[j] < rating[i]:\n",
    "                    right_smaller += 1\n",
    "                else :\n",
    "                    right_larger += 1\n",
    "\n",
    "            result += left_smaller * right_larger + left_larger * right_smaller\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        a = len(rating)\n",
    "        sum = 0\n",
    "        for i in range(1, a-1):    # i从1便历到8\n",
    "            zuo = 0\n",
    "            you = a-1\n",
    "            zuoxiao, youxiao = 0, 0\n",
    "            zuoda, youda = 0, 0\n",
    "            while zuo < i:\n",
    "                if rating[zuo] < rating[i]:\n",
    "                    zuoxiao += 1\n",
    "                else:\n",
    "                    zuoda += 1\n",
    "                zuo += 1\n",
    "            while you > i:\n",
    "                if rating[i] > rating[you]:\n",
    "                    youxiao += 1\n",
    "                else:\n",
    "                    youda += 1\n",
    "                you -= 1\n",
    "            sum += zuoxiao*youda+zuoda*youxiao\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        result = 0\n",
    "\n",
    "        for i in range(1, n-1):  # 只从数组的两端开始遍历\n",
    "            left_smaller, left_larger = 0, 0\n",
    "            right_smaller, right_larger = 0, 0\n",
    "\n",
    "            for j in range(i):\n",
    "                if rating[j] < rating[i]:\n",
    "                    left_smaller += 1\n",
    "                else:\n",
    "                    left_larger += 1\n",
    "\n",
    "            for j in range(i + 1, n):\n",
    "                if rating[j] < rating[i]:\n",
    "                    right_smaller += 1\n",
    "                else :\n",
    "                    right_larger += 1\n",
    "\n",
    "            result += left_smaller * right_larger + left_larger * right_smaller\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "        self.path = []\n",
    "\n",
    "    def numTeams(self, rating) -> int:\n",
    "        # 3层For循环，盲猜超时\n",
    "\n",
    "        #深搜也超时\n",
    "        # n = len(rating)\n",
    "\n",
    "        # def dfs(start_idx, n):\n",
    "        #     if len(self.path) == 3:\n",
    "        #         if self.path[0] < self.path[1] < self.path[2] or self.path[0] > self.path[1] > self.path[2]:\n",
    "        #             self.res += 1\n",
    "        #         return\n",
    "        #     for i in range(start_idx, n):\n",
    "        #         self.path.append(rating[i])\n",
    "        #         dfs(i + 1, n)\n",
    "        #         self.path.pop()\n",
    "\n",
    "        # dfs(0, n)\n",
    "        # return self.res\n",
    "\n",
    "        # 参考题解\n",
    "        ans=0\n",
    "        n=len(rating)\n",
    "        for j in range(1,n-1):\n",
    "            left_less,left_more,right_more,right_less=0,0,0,0\n",
    "            for i in range(j):\n",
    "                if rating[i]<rating[j]:\n",
    "                    left_less+=1\n",
    "                else:\n",
    "                    left_more+=1\n",
    "            for i in range(j+1,n):\n",
    "                if rating[i]<rating[j]:\n",
    "                    right_less+=1\n",
    "                else:\n",
    "                    right_more+=1\n",
    "            ans+=left_less*right_more+left_more*right_less\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        dp = [0]*n\n",
    "        rec = [[0]*2 for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            for j in range(0,i):\n",
    "                if rating[j]<rating[i]:\n",
    "                    rec[i][0] += 1\n",
    "                else:\n",
    "                    rec[i][1] += 1\n",
    "        \n",
    "        for i in range(2, n):\n",
    "            for j in range(0, i):\n",
    "                if rating[j] < rating[i]:\n",
    "                    dp[i] += rec[j][0]\n",
    "                else:\n",
    "                    dp[i] += rec[j][1]\n",
    "                pass\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        # 中心扩散\n",
    "        ans = 0\n",
    "        iLess, iMore, kLess, kMore = 0, 0, 0, 0\n",
    "        n = len(rating)\n",
    "        for j in range(n):\n",
    "            i = j - 1\n",
    "            iLess, iMore, kLess, kMore = 0, 0, 0, 0\n",
    "            while i >= 0:\n",
    "                if rating[i] < rating[j]:\n",
    "                    iLess += 1\n",
    "                else:\n",
    "                    iMore += 1\n",
    "                i -= 1\n",
    "            k = j + 1\n",
    "            while k < n:\n",
    "                if rating[k] < rating[j]:\n",
    "                    kLess += 1\n",
    "                else:\n",
    "                    kMore += 1\n",
    "                k += 1\n",
    "            ans += iLess*kMore + iMore*kLess\n",
    "            j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        result = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            left_smaller, left_larger = 0, 0\n",
    "            right_smaller, right_larger = 0, 0\n",
    "\n",
    "            for j in range(i):\n",
    "                if rating[j] < rating[i]:\n",
    "                    left_smaller += 1\n",
    "                elif rating[j] > rating[i]:\n",
    "                    left_larger += 1\n",
    "\n",
    "            for j in range(i + 1, n):\n",
    "                if rating[j] < rating[i]:\n",
    "                    right_smaller += 1\n",
    "                elif rating[j] > rating[i]:\n",
    "                    right_larger += 1\n",
    "\n",
    "            result += left_smaller * right_larger + left_larger * right_smaller\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        ans = 0\n",
    "        for j in range(1, n-1):\n",
    "            iless = imore = kless = kmore = 0\n",
    "            for i in range(j):\n",
    "                if rating[i] < rating[j]:\n",
    "                    iless += 1\n",
    "                elif rating[i] > rating[j]:\n",
    "                    imore += 1\n",
    "            for k in range(j+1, n):\n",
    "                if rating[k] < rating[j]:\n",
    "                    kless += 1\n",
    "                elif rating[k] > rating[j]:\n",
    "                    kmore += 1\n",
    "            # print(iless, imore, kless, kmore)\n",
    "            ans += iless * kmore + imore * kless\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numTeams(self, rating: List[int]) -> int:\r\n",
    "        n = len(rating)\r\n",
    "        ans = 0\r\n",
    "        for i in range(1,n - 1):\r\n",
    "            left = [0,0]\r\n",
    "            right = [0,0]\r\n",
    "            for j in range(i):\r\n",
    "                if rating[j] < rating[i]:\r\n",
    "                    left[0] += 1\r\n",
    "                elif rating[j] > rating[i]:\r\n",
    "                    left[1] += 1\r\n",
    "            for k in range(i + 1, n):\r\n",
    "                if rating[k] < rating[i]:\r\n",
    "                    right[0] += 1\r\n",
    "                elif rating[k] > rating[i]:\r\n",
    "                    right[1] += 1\r\n",
    "            ans += left[0] * right[1] + left[1] * right[0]\r\n",
    "        return ans\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        def func(rating):\n",
    "            dp = [[0, 0] for _ in range(n)]\n",
    "            for i in range(1, n):\n",
    "                for j in range(i):\n",
    "                    if rating[i] > rating[j]:\n",
    "                        dp[i][0] += 1\n",
    "                        dp[i][1] += dp[j][0]\n",
    "            ans = 0\n",
    "            for i in range(2, n):\n",
    "                ans += dp[i][1]\n",
    "            return ans\n",
    "        \n",
    "        a = func(rating)\n",
    "        rating.reverse()\n",
    "        b = func(rating)\n",
    "        return a + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        def func(rating):\n",
    "            dp = [[0, 0] for _ in range(n)]\n",
    "            for i in range(1, n):\n",
    "                for j in range(i):\n",
    "                    if rating[i] > rating[j]:\n",
    "                        dp[i][0] += 1\n",
    "                        dp[i][1] += dp[j][0]\n",
    "            ans = 0\n",
    "            for i in range(2, n):\n",
    "                ans += dp[i][1]\n",
    "            return ans\n",
    "        \n",
    "        a = func(rating)\n",
    "        rating.reverse()\n",
    "        b = func(rating)\n",
    "        return a + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        # ans=0\n",
    "        # n=len(rating)\n",
    "        # for i in range(n):\n",
    "        #     rightmax=0\n",
    "        #     rightmin=0\n",
    "        #     leftmax=0\n",
    "        #     leftmin=0\n",
    "        #     num=rating[i]\n",
    "        #     for j in range(i):\n",
    "        #         if rating[j]>num:\n",
    "        #             leftmax+=1\n",
    "        #         if rating[j]<num:\n",
    "        #             leftmin+=1\n",
    "            \n",
    "        #     for k in range(i+1,n):\n",
    "        #         if rating[k]>num:\n",
    "        #             rightmax+=1\n",
    "        #         if rating[k]<num:\n",
    "        #             rightmin+=1\n",
    "        #     ans+=leftmax*rightmin+leftmin*rightmax\n",
    "        # return ans\n",
    "\n",
    "        \n",
    "        def lowbit(x):          # lowbit函数：二进制最低位1所表示的数字\n",
    "            return x & (-x)\n",
    "\n",
    "        def add(i, delta):      # 单点更新：执行+delta\n",
    "            while i<len(tree):\n",
    "                tree[i] += delta\n",
    "                i += lowbit(i)\n",
    "\n",
    "        def query(i):           # 前缀和查询\n",
    "            presum = 0\n",
    "            while i>0:\n",
    "                presum += tree[i]\n",
    "                i -= lowbit(i)\n",
    "            return presum\n",
    "\n",
    "\n",
    "        '''主程序'''\n",
    "        # 离散化：绝对数值转秩次rank\n",
    "        uniques = sorted(rating)    # rating没有重复值\n",
    "        rank_map = {v:i+1 for i,v in enumerate(uniques)}    #【rank从1开始】\n",
    "        \n",
    "        # 构建树状数组\n",
    "        tree = [0] * (len(rank_map) + 1)    # 树状数组下标从1开始\n",
    "\n",
    "        # 枚举中间点\n",
    "        ans = 0\n",
    "        n = len(rating)\n",
    "        add(rank_map[rating[0]], 1)     # 先将第一个元素入列\n",
    "        for i in range(1, n-1):         # 从第二个元素开始遍历，直至倒数第二个元素\n",
    "            rank = rank_map[rating[i]]  # 当前元素的排名/秩次\n",
    "\n",
    "            small1 = query(rank-1)      # 查询前序元素中排名<rank的元素数目\n",
    "            large1 = i - small1         # small1 + large1 = i\n",
    "\n",
    "            small2 = (rank-1) - small1  # 共有rank-1个元素排名<rank：small1 + small2 = rank-1\n",
    "            large2 = n-1 - i - small2   # small2 + large2 = n-1-i\n",
    "\n",
    "            add(rank, 1)                # 当前元素入列\n",
    "\n",
    "            ans += small1*large2 + large1*small2\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n=len(rating)\n",
    "        bigl=[0]*n\n",
    "        bigr=[0]*n\n",
    "        smalll=[0]*n \n",
    "        smallr=[0]*n \n",
    "        stack1=[]\n",
    "        stack2=[]\n",
    "    \n",
    "        for i in range(n):\n",
    "\n",
    "            bigl[i]=len(stack1)-bisect.bisect_right(stack1,rating[i])\n",
    "            smalll[i]=bisect.bisect_left(stack1,rating[i])\n",
    "            bisect.insort_left(stack1,rating[i])\n",
    "           \n",
    "        stack1=[]\n",
    "        stack2=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            bigr[i]=len(stack1)-bisect.bisect_right(stack1,rating[i])\n",
    "            smallr[i]=bisect.bisect_left(stack1,rating[i])\n",
    "            bisect.insort_left(stack1,rating[i])\n",
    "        ans=0\n",
    "        for i in range(1,n-1):\n",
    "            if bigr[i]>0 and smalll[i]>0:\n",
    "                ans+=bigr[i]*smalll[i]\n",
    "            if bigl[i]>0 and smallr[i]>0:\n",
    "                ans+=bigl[i]*smallr[i]\n",
    "        \n",
    "      \n",
    "\n",
    "\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        ans=0\n",
    "        n=len(rating)\n",
    "        for i in range(n):\n",
    "            a=rating[i]\n",
    "            lst1=rating[:i][:]\n",
    "            lst2=rating[i+1:][:]\n",
    "            lst1.sort()\n",
    "            lst2.sort()\n",
    "            b=bisect_left(lst1,a)\n",
    "            c=bisect_left(lst2,a)\n",
    "            ans+=b*(n-1-i-c)+(i-b)*(c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        #中心扩展\n",
    "        left_smaller = [0]*n\n",
    "        right_smaller = [0]*n\n",
    "        left_larger = [0]*n\n",
    "        right_larger = [0]*n\n",
    "        for i in range(n):\n",
    "            small,large = 0,0\n",
    "            for x in rating[:i]:\n",
    "                if x<rating[i]:left_smaller[i]+=1\n",
    "                elif x>rating[i]:left_larger[i]+=1\n",
    "            for y in rating[i+1:]:\n",
    "                if y<rating[i]:right_smaller[i]+=1\n",
    "                elif y>rating[i]:right_larger[i]+=1\n",
    "        res = 0 \n",
    "        for i in range(n):\n",
    "            res+=left_larger[i]*right_smaller[i]\n",
    "            res+=left_smaller[i]*right_larger[i]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n = len(rating)\n",
    "        def func(rating):\n",
    "            dp = [[0, 0] for _ in range(n)]\n",
    "            for i in range(1, n):\n",
    "                for j in range(i):\n",
    "                    if rating[i] > rating[j]:\n",
    "                        dp[i][0] += 1\n",
    "                        dp[i][1] += dp[j][0]\n",
    "            ans = 0\n",
    "            for i in range(2, n):\n",
    "                ans += dp[i][1]\n",
    "            return ans\n",
    "        \n",
    "        a = func(rating)\n",
    "        rating.reverse()\n",
    "        b = func(rating)\n",
    "        return a + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        length = len(rating) + 1\n",
    "        # 离散化\n",
    "        temp = sorted((n, i) for i, n in enumerate(rating))\n",
    "        for new, ( _, i) in enumerate(temp, 1):\n",
    "            rating[i] = new\n",
    "        del temp\n",
    "        # 树状数组\n",
    "        tree = [0] * length\n",
    "\n",
    "        def lowbit(x):\n",
    "            return x & (-x)\n",
    "\n",
    "        def add(pos):\n",
    "            while pos < length:\n",
    "                tree[pos] += 1\n",
    "                pos += lowbit(pos)\n",
    "\n",
    "        def query(pos):\n",
    "            res = 0\n",
    "            while pos > 0:\n",
    "                res += tree[pos]\n",
    "                pos -= lowbit(pos)\n",
    "            return res\n",
    "\n",
    "        ans = 0\n",
    "        # 先入列第一个元素\n",
    "        add(rating[0])\n",
    "        # 从第二个元素遍历到倒数第二个\n",
    "        for i, n in enumerate(rating[1:-1], 1):\n",
    "            small_left = query(n)\n",
    "            large_left = i - small_left\n",
    "            small_right = n - 1 - small_left\n",
    "            large_right = length - 1 - n - large_left\n",
    "            ans += small_left * large_right + small_right * large_left\n",
    "            add(n)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        # ans=0\n",
    "        # n=len(rating)\n",
    "        # for i in range(n):\n",
    "        #     rightmax=0\n",
    "        #     rightmin=0\n",
    "        #     leftmax=0\n",
    "        #     leftmin=0\n",
    "        #     num=rating[i]\n",
    "        #     for j in range(i):\n",
    "        #         if rating[j]>num:\n",
    "        #             leftmax+=1\n",
    "        #         if rating[j]<num:\n",
    "        #             leftmin+=1\n",
    "            \n",
    "        #     for k in range(i+1,n):\n",
    "        #         if rating[k]>num:\n",
    "        #             rightmax+=1\n",
    "        #         if rating[k]<num:\n",
    "        #             rightmin+=1\n",
    "        #     ans+=leftmax*rightmin+leftmin*rightmax\n",
    "        # return ans\n",
    "\n",
    "        \n",
    "        def lowbit(x):          # lowbit函数：二进制最低位1所表示的数字\n",
    "            return x & (-x)\n",
    "\n",
    "        def add(i, delta):      # 单点更新：执行+delta\n",
    "            while i<len(tree):\n",
    "                tree[i] += delta\n",
    "                i += lowbit(i)\n",
    "\n",
    "        def query(i):           # 前缀和查询\n",
    "            presum = 0\n",
    "            while i>0:\n",
    "                presum += tree[i]\n",
    "                i -= lowbit(i)\n",
    "            return presum\n",
    "\n",
    "\n",
    "        '''主程序'''\n",
    "        # 离散化：绝对数值转秩次rank\n",
    "        uniques = sorted(rating)    # rating没有重复值\n",
    "        rank_map = {v:i+1 for i,v in enumerate(uniques)}    #【rank从1开始】\n",
    "        print(rank_map)\n",
    "        # 构建树状数组\n",
    "        tree = [0] * (len(rank_map) + 1)    # 树状数组下标从1开始\n",
    "\n",
    "        # 枚举中间点\n",
    "        ans = 0\n",
    "        n = len(rating)\n",
    "        add(rank_map[rating[0]], 1)     # 先将第一个元素入列\n",
    "        for i in range(1, n):         # 从第二个元素开始遍历，直至倒数第二个元素\n",
    "            rank = rank_map[rating[i]]  # 当前元素的排名/秩次\n",
    "\n",
    "            small1 = query(rank-1)      # 查询前序元素中排名<rank的元素数目\n",
    "            large1 = i - small1         # small1 + large1 = i\n",
    "\n",
    "            small2 = (rank-1) - small1  # 共有rank-1个元素排名<rank：small1 + small2 = rank-1\n",
    "            large2 = n-1 - i - small2   # small2 + large2 = n-1-i\n",
    "\n",
    "            add(rank, 1)                # 当前元素入列\n",
    "\n",
    "            ans += small1*large2 + large1*small2\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        # ans=0\n",
    "        # n=len(rating)\n",
    "        # for i in range(n):\n",
    "        #     rightmax=0\n",
    "        #     rightmin=0\n",
    "        #     leftmax=0\n",
    "        #     leftmin=0\n",
    "        #     num=rating[i]\n",
    "        #     for j in range(i):\n",
    "        #         if rating[j]>num:\n",
    "        #             leftmax+=1\n",
    "        #         if rating[j]<num:\n",
    "        #             leftmin+=1\n",
    "            \n",
    "        #     for k in range(i+1,n):\n",
    "        #         if rating[k]>num:\n",
    "        #             rightmax+=1\n",
    "        #         if rating[k]<num:\n",
    "        #             rightmin+=1\n",
    "        #     ans+=leftmax*rightmin+leftmin*rightmax\n",
    "        # return ans\n",
    "\n",
    "        \n",
    "        def lowbit(x):          # lowbit函数：二进制最低位1所表示的数字\n",
    "            return x & (-x)\n",
    "\n",
    "        def add(i, delta):      # 单点更新：执行+delta\n",
    "            while i<len(tree):\n",
    "                tree[i] += delta\n",
    "                i += lowbit(i)\n",
    "\n",
    "        def query(i):           # 前缀和查询\n",
    "            presum = 0\n",
    "            while i>0:\n",
    "                presum += tree[i]\n",
    "                i -= lowbit(i)\n",
    "            return presum\n",
    "\n",
    "\n",
    "        '''主程序'''\n",
    "        # 离散化：绝对数值转秩次rank\n",
    "        uniques = sorted(rating)    # rating没有重复值\n",
    "        rank_map = {v:i+1 for i,v in enumerate(uniques)}    #【rank从1开始】\n",
    "        print(rank_map)\n",
    "        # 构建树状数组\n",
    "        tree = [0] * (len(rank_map) + 1)    # 树状数组下标从1开始\n",
    "\n",
    "        # 枚举中间点\n",
    "        ans = 0\n",
    "        n = len(rating)\n",
    "        # add(rank_map[rating[0]], 1)     # 先将第一个元素入列\n",
    "        for i in range(n):         # 从第二个元素开始遍历，直至倒数第二个元素\n",
    "            rank = rank_map[rating[i]]  # 当前元素的排名/秩次\n",
    "\n",
    "            small1 = query(rank-1)      # 查询前序元素中排名<rank的元素数目\n",
    "            large1 = i - small1         # small1 + large1 = i\n",
    "\n",
    "            small2 = (rank-1) - small1  # 共有rank-1个元素排名<rank：small1 + small2 = rank-1\n",
    "            large2 = n-1 - i - small2   # small2 + large2 = n-1-i\n",
    "\n",
    "            add(rank, 1)                # 当前元素入列\n",
    "\n",
    "            ans += small1*large2 + large1*small2\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        ##统计j左右两侧\n",
    "        n=len(rating)\n",
    "        leftgreater=[0]*n##左侧大于当前元素的数量\n",
    "        rightgreater=[0]*n##\n",
    "        # stack=[]\n",
    "        # for i,r in enumerate(rating):\n",
    "        #     while stack and rating[stack[-1]]<r:##保证元素递减\n",
    "        #         stack.pop()\n",
    "        #     leftgreater[i]=len(stack)\n",
    "        #     stack.append(i)\n",
    "        # stack=[]\n",
    "        # for i in range(n-1,-1,-1):\n",
    "        #     while stack and rating[stack[-1]]<rating[i]:##保证元素递减\n",
    "        #         stack.pop()\n",
    "        #     rightgreater[i]=len(stack)\n",
    "        #     stack.append(i)\n",
    "        # print(leftgreater,rightgreater)\n",
    "\n",
    "\n",
    "\n",
    "        arr=SortedList()\n",
    "        for i in range(n):\n",
    "            j=bisect_left(arr,rating[i])\n",
    "            leftgreater[i]=len(arr)-j\n",
    "            arr.add(rating[i])\n",
    "        arr=SortedList()\n",
    "        for i in range(n-1,-1,-1):\n",
    "            j=bisect_left(arr,rating[i])\n",
    "            rightgreater[i]=len(arr)-j\n",
    "            arr.add(rating[i])\n",
    "        # print(leftgreater,rightgreater)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            ans+= (i-leftgreater[i])*rightgreater[i]\n",
    "            ans+= leftgreater[i]*(n-i-1-rightgreater[i])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Bit:\n",
    "    def __init__(self):\n",
    "        self.n = 1005\n",
    "        self.bit = [0]*self.n\n",
    "    \n",
    "    def lowbit(self, x:int)->int:\n",
    "        return x & (-x)\n",
    "    \n",
    "    def update(self, p:int, v:int):\n",
    "        while p <= self.n:\n",
    "           # print(\"update\", p)\n",
    "            self.bit[p] += v\n",
    "            p += self.lowbit(p)\n",
    "    \n",
    "    def query(self, x:int)->int:\n",
    "        ans = 0\n",
    "        while x:\n",
    "            #print(\"query\")\n",
    "            ans += self.bit[x]\n",
    "            x -= self.lowbit(x)\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        sortRating = [ i for i in rating]\n",
    "        sortRating.append(-1)\n",
    "        sortRating.sort()\n",
    "        #print(sortRating)\n",
    "        #print(rating)\n",
    "        n = len(rating)\n",
    "        iLess, iMore = [0]*n, [0]*n\n",
    "        bit = Bit()\n",
    "        for i in range(n):\n",
    "            val = rating[i]\n",
    "            pos = bisect.bisect_left(sortRating, val)\n",
    "            #print(\"1111\", pos)\n",
    "            iLess[i] = bit.query(pos)\n",
    "            iMore[i] = bit.query(1002) - iLess[i]\n",
    "            bit.update(pos, 1)\n",
    "        \n",
    "        bit.bit = [0]*bit.n\n",
    "        kLess, kMore = [0]*n, [0]*n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            val = rating[i]\n",
    "            pos = bisect.bisect_left(sortRating, val)\n",
    "            #print(\"2222\", pos)\n",
    "            kLess[i] = bit.query(pos)\n",
    "            kMore[i] = bit.query(1002) - kLess[i]\n",
    "            bit.update(pos, 1)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += iLess[i]*kMore[i] + iMore[i]*kLess[i]\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        n=len(rating)\n",
    "        leftless=[0]*n##左侧小于当前元素的数量\n",
    "        rightless=[0]*n##右侧小于当前元素的数量\n",
    "        def calculate(start,end,step,cnt:list[int]):\n",
    "            arr=SortedList()\n",
    "            for i in range(start,end,step):\n",
    "                j=bisect_left(arr,rating[i])\n",
    "                cnt[i]=j\n",
    "                arr.add(rating[i])\n",
    "        calculate(0,n,1,leftless)\n",
    "        calculate(n-1,-1,-1,rightless)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            ans+= (i-leftless[i])*rightless[i]\n",
    "            ans+= leftless[i]*(n-i-1-rightless[i])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        ##统计j左右两侧\n",
    "        n=len(rating)\n",
    "        leftless=[0]*n##左侧大于当前元素的数量\n",
    "        rightless=[0]*n\n",
    "        arr=SortedList()\n",
    "        for i in range(n):\n",
    "            j=bisect_left(arr,rating[i])\n",
    "            leftless[i]=j\n",
    "            arr.add(rating[i])\n",
    "        arr=SortedList()\n",
    "        for i in range(n-1,-1,-1):\n",
    "            j=bisect_left(arr,rating[i])\n",
    "            rightless[i]=j\n",
    "            arr.add(rating[i])\n",
    "        # print(leftgreater,rightgreater)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            ans+= (i-leftless[i])*rightless[i]\n",
    "            ans+= leftless[i]*(n-i-1-rightless[i])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "class Solution:\n",
    "    def f(self, rating):\n",
    "        l, c, res = sortedcontainers.SortedList(rating), [], 0\n",
    "        c = []\n",
    "        for i in rating:\n",
    "            p = l.bisect_left(i)\n",
    "            l.discard(i)\n",
    "            c.append((i, len(l)-p))\n",
    "        for i in rating:\n",
    "            for cnt, j in enumerate(c):\n",
    "                if i<j[0]: res += j[1]\n",
    "                if i==j[0]: p=cnt\n",
    "            c.pop(p)\n",
    "        return res\n",
    "\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        return self.f(rating) + self.f(rating[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "class Solution:\n",
    "    def f(self, rating):\n",
    "        l, c, res = sortedcontainers.SortedList(rating), sortedcontainers.SortedList(), 0\n",
    "        for i in rating:\n",
    "            p = l.bisect_left(i)\n",
    "            l.discard(i)\n",
    "            c.add((i, len(l)-p))\n",
    "        for i in rating:\n",
    "            p = c.bisect_left((i, -1))\n",
    "            res += sum(c[j][1] for j in range(p+1, len(c)))\n",
    "            c.pop(p)\n",
    "        return res\n",
    "\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        return self.f(rating) + self.f(rating[::-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: List[int]) -> int:\n",
    "        left_le = []\n",
    "        left_ge = []\n",
    "        nset_le = SortedList()\n",
    "        nset_ge = SortedList(key=lambda x: -x)\n",
    "        for u in rating:\n",
    "            left_le.append(nset_le.bisect_left(u))\n",
    "            left_ge.append(nset_ge.bisect_left(u))\n",
    "            nset_le.add(u)\n",
    "            nset_ge.add(u)\n",
    "        right_le = []\n",
    "        right_ge = []\n",
    "        nset_le = SortedList()\n",
    "        nset_ge = SortedList(key=lambda x: -x)\n",
    "        for u in reversed(rating):\n",
    "            right_le.append(nset_le.bisect_left(u))\n",
    "            right_ge.append(nset_ge.bisect_left(u))\n",
    "            nset_le.add(u)\n",
    "            nset_ge.add(u)\n",
    "        cnt = 0\n",
    "        for lle, lge, rle, rge in zip(left_le, left_ge, reversed(right_le), reversed(right_ge)):\n",
    "            cnt += lle * rge + lge * rle\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numTeams(self, rating: list[int]) -> int:\n",
    "        def  find1(index,prerate,n):\n",
    "            if n==1:\n",
    "                self.ans+=bigger[index-1]\n",
    "                return \n",
    "            for i in range(index,len(rating)):\n",
    "                if rating[i]>prerate:\n",
    "                    find1(i+1,rating[i],n-1)\n",
    "\n",
    "        def  find2(index,prerate,n):\n",
    "            if n==1:\n",
    "                self.ans+=smaller[index-1]\n",
    "                return \n",
    "            for i in range(index,len(rating)):\n",
    "                if rating[i]<prerate:\n",
    "                    find2(i+1,rating[i],n-1)\n",
    "        bigger=[0 for i in range(len(rating))]\n",
    "        smaller=[0 for i in range(len(rating))]\n",
    "        for i in range(len(rating)):\n",
    "            for j in range(i+1,len(rating)):\n",
    "                if rating[j]>rating[i]:\n",
    "                    bigger[i]+=1\n",
    "                if rating[j]<rating[i]:\n",
    "                    smaller[i]+=1\n",
    "        self.ans = 0\n",
    "        find1(0,0,3)\n",
    "        find2(0,100005,3)\n",
    "        return self.ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
